package listbyorder.access201_300.test222;

import listbyorder.utils.TreeNode;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/7/30 20:46
 */
public class Solution1 {

    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        int h = getH(root);
        return dfs(root, 1, h);
    }

    // 计算树的高度
    private int getH(TreeNode root) {
        if (root == null) return 0;
        int res = 1;
        while (root.left != null) {
            root = root.left;
            res++;
        }
        return res;
    }

    // 求解
    private int dfs(TreeNode root, int level, int h) {
        if (level == h) return 1;
        // 首先计算右子树的高度
        int rH = getH(root.right);
        if (level + rH == h) {
            return (1 << (h - level)) + dfs(root.right, level + 1, h);
        } else {
            return dfs(root.left, level + 1, h) + (1 << (h - level - 1));
        }
    }
}
